#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};
#ifndef COMPILER_ONLINE

#include "header.cpp"

#endif
int ans_count = 0;

void Test1()
{
    string s = "barfoothefoobarman";
    vector<string> words{"foo","bar"};
    //通过定义临时对象，来完成方法的调用
    vector<int> ans;
    ans = Solution().findSubstring(s,words);
    if((ans[0] == 0 && ans[1] == 9) || (ans[0] == 9 && ans[1] == 0))
    {
        cout << "测试用例1 ...通过! 测试用例为 s = \"barfoothefoobarman\",words:[\"foo\",\"bar\"] "<< endl;
        ans_count++;
    }
    else
    {
        cout << "测试用例1 ...失败!  s = \"barfoothefoobarman\",words:[\"foo\",\"bar\"]" << endl;
    }
}
void Test2()
{
    string s = "wordgoodgoodgoodbestword";
    vector<string> words{"word","good","best","word"};
    //通过定义临时对象，来完成方法的调用
    vector<int> ans;
    ans = Solution().findSubstring(s,words);
    if(ans.size() == 0)
    {
        cout << "测试用例2 ...通过! 测试用例为 s = \"wordgoodgoodgoodbestword\",words:[\"word\",\"good\",\"best\",\"word\"] "<< endl;
        ans_count++;
    }
    else
    {
        cout << "测试用例2 ...失败! 测试用例为 s = \"wordgoodgoodgoodbestword\",words:[\"word\",\"good\",\"best\",\"word\"] "<< endl;
    }
}
void Test3()
{
    string s = "barfoofoobarthefoobarman";
    vector<string> words{"bar","foo","the"};
    //通过定义临时对象，来完成方法的调用
    vector<int> ans;
    ans = Solution().findSubstring(s,words);
    if(ans[0] == 6 && ans[1] == 9 && ans[2] == 12)
    {
        cout << "测试用例3 ...通过! 测试用例为 s = \"barfoofoobarthefoobarman\",words:[\"bar\",\"foo\",\"the\"] "<< endl;
        ans_count++;
    }
    else
    {
        cout << "测试用例3 ...失败! 测试用例为 s = \"barfoofoobarthefoobarman\",words:[\"bar\",\"foo\",\"the\"] "<< endl;
    }
}
int main()
{
    Test1();
    Test2();
    Test3();
    if(ans_count == 3) cout << "恭喜你，通过全部测试用例！本题通过！" << endl;

}